package cn.edu.ncepu;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ExtendedEuclidBigInteger {

    public static BigInteger[] extendEuclid(BigInteger a, BigInteger b) {
        if (a.compareTo(b) < 0) {
            BigInteger[] temp = extendEuclid(b, a);
            return new BigInteger[]{temp[1], temp[0]};
        }

        List<BigInteger> coefficients = new ArrayList<>();
        BigInteger originalA = a;
        BigInteger originalB = b;

        while (b.compareTo(BigInteger.ZERO) != 0) {
            coefficients.add(a.divide(b));
            BigInteger temp = b;
            b = a.mod(b);
            a = temp;
        }

        BigInteger x = BigInteger.ONE;
        BigInteger y = BigInteger.ZERO;
        Collections.reverse(coefficients);

        for (BigInteger i : coefficients) {
            BigInteger tempX = x;
            x = y;
            y = tempX.subtract(y.multiply(i));
        }

        return new BigInteger[]{x, y};
    }

    public static BigInteger modularInverse(BigInteger a, BigInteger m) {
        BigInteger[] result = extendEuclid(a, m);
        BigInteger x = result[0];

        while (x.compareTo(BigInteger.ZERO) < 0) {
            x = x.add(m);
        }

        return x;
    }

    public static void main(String[] args) {
        BigInteger a = BigInteger.valueOf(3);
        BigInteger m = BigInteger.valueOf(7);
        BigInteger x = modularInverse(a, m);
        System.out.printf("%s * %s %% %s = %s%n", a, x, m, a.multiply(x).mod(m));
    }
}